package seventhweek;

import fourthweek.Array.ArrayUnorderedList;
import fourthweek.ElementNotFoundException;
import fourthweek.UnorderedListADT;
import secondweek.EmptyCollectionException;

import java.util.*;

/**
 * LinkedBinaryTree implements the BinaryTreeADT interface
 *
 * @author Lewis and Chase
 * @version 4.0
 */

public class LinkedBinaryTree<T> implements Iterable<T>, BinaryTreeADT<T> {

    protected BinaryTreeNode<T> root;
    protected int modCount;
    private LinkedBinaryTree<T> left, right;
    /**
     * Creates an empty binary tree.
     */
    public LinkedBinaryTree() {
        root = null;
    }
    /**
     * Creates a binary tree with the specified element as its root.
     *
     * @param element the element that will become the root of the binary tree
     */
    public LinkedBinaryTree(T element) {
        root = new BinaryTreeNode<T>(element);
    }
    /**
     * Creates a binary tree with the specified element as its root and the given trees as its left child and right child.
     *
     * @param element the element that will become the root of the binary tree
     * @param left the left subtree of this tree
     * @param right the right subtree of this tree
     */    public LinkedBinaryTree(T element, LinkedBinaryTree<T> left, LinkedBinaryTree<T> right) {
        root = new BinaryTreeNode<T>(element);
        root.setLeft(left.root);
        root.setRight(right.root);
        this.left = left;
        this.right = right;
    }

    public BinaryTreeNode<T> getRootNode() throws EmptyCollectionException {
        if (isEmpty()) {
            throw new EmptyCollectionException("BinaryTreeNode ");
        }
        return root;
    }
    //返回某结点的左侧子结点
    public LinkedBinaryTree<T> getLeft() {
        return left;
     }
    //返回某结点的右侧子结点
    public LinkedBinaryTree<T> getRight() {
        return right;
     }
    public int getHeight1() {
        BinaryTreeNode temp = root;
        int height = 1;
        if(root == null )
            return 0;
        if (root != null){
            height++;
        }
        temp = temp.left;
        while (temp.internalNode() != true){
            height++;
            temp = temp.left;
        }
        height++;
        return height + 1;
    }

    @Override
    public T getRootElement() throws EmptyCollectionException {
        if (root.getElement().equals(null)) {
            throw new EmptyCollectionException("BinaryTreeNode ");
        }
        return root.getElement();
    }

    @Override
    public boolean isEmpty() {
        return (root == null);
    }

    @Override
    public int size() {
        int size = 0;
        if(root.getLeft()!=null)
            size+=1;
        if(root.getRight()!=null)
            size+=1;
        return size;
    }
    public int getHeight2(){
        return getheight(root) + 1;
    }
    private int getheight(BinaryTreeNode<T> temp){
        //如果树为空的话，就返回-1，在getHeight方法内进行加1，这样就为0。
        if(temp == null)
            return -1;
        //如果树只有根结点的话，就返回0，在getHeight方法内进行加1，这样就为1。
        if(!temp.internalNode())
            return 0;
        int leftChildHeight = getheight(temp.getLeft());
        int rightChildHeight = getheight(temp.getRight());
        return Math.max(leftChildHeight,rightChildHeight) + 1;
    }
    public int CountLeaf(BinaryTreeNode<T> temp){
        //如果该树是空的，则输出0个叶结点
        if(temp == null)
            return 0;
        //如果该树只有根结点
        if(!temp.internalNode()){
           return 1;
        }else{
            //如果该树不是内部结点的话，就调左子结点和右子结点进行递归
            return CountLeaf(temp.left) + CountLeaf(temp.right);
        }
    }

    @Override
    //判断是否包含某个元素
    public boolean contains(T targetElement) {
        if(targetElement == find(targetElement))
            return true;
        else
            return false;
    }

    /**
     *  Returns a reference to the specified target element if it is found in this binary tree.
     *  Throws a NoSuchElementException if the specified target element is not found in the binary tree.
     *
     * @param targetElement the element being sought in the tree
     * @return a reference to the specified target
     * @throws ElementNotFoundException if an element not found exception occurs
     */
    public T find(T targetElement) {
        BinaryTreeNode<T> current = findNode(targetElement, root);

        if (current == null)
            throw new ElementNotFoundException("LinkedBinaryTree");

        return (current.getElement());
    }

    /**
     * Returns a reference to the specified target element if it is found in this binary tree.
     *
     * @param targetElement the element being sought in this tree
     * @param next the element to begin searching from
     */
    private BinaryTreeNode<T> findNode(T targetElement, BinaryTreeNode<T> next) {
        if (next == null)
            return null;
//根结点
        if (next.getElement().equals(targetElement))
            return next;
//左结点
        BinaryTreeNode<T> temp = findNode(targetElement, next.getLeft());
//右结点
        if (temp == null)
            temp = findNode(targetElement, next.getRight());

        return temp;
    }

    //删除二叉树某结点的右侧部分
    public void removeRightSubtree(T node){
        BinaryTreeNode<T> next = new BinaryTreeNode<T>(node);
        if(root == null)
            throw new EmptyCollectionException("Tree is Empty!!");
        if((T) next.getRight() == null)
            System.out.println("删除位置没有右枝杈！！");
        else
            next.setRight(null);
    }

    //删除二叉树中全部元素
    public void removeElement(){
        BinaryTreeNode<T> root = null;
        this.root = root;
    }

    @Override
    //为树的中序遍历返回一个迭代器
    public Iterator<T> iteratorInOrder() {
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        inOrder(root, tempList);
        return new TreeIterator(tempList.iterator());
    }
    protected void inOrder(BinaryTreeNode<T> node, ArrayUnorderedList<T> tempList) {
        if (node != null) {
            inOrder(node.getLeft(), tempList);
            tempList.addToRear(node.getElement());
            inOrder(node.getRight(), tempList);
        }
    }

    @Override
    //为树的前序遍历返回一个迭代器
    public Iterator<T> iteratorPreOrder() {
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        preOrder(root, tempList);
        return new TreeIterator(tempList.iterator());
    }
    private void preOrder(BinaryTreeNode<T> node, ArrayUnorderedList<T> tempList) {
        if (node != null) {
            tempList.addToRear(node.getElement());
            inOrder(node.getLeft(), tempList);
            inOrder(node.getRight(), tempList);
        }
    }

    @Override
    //为树的后序遍历返回一个迭代器
    public Iterator<T> iteratorPostOrder() {
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        postOrder(root, tempList);
        return new TreeIterator(tempList.iterator());
    }
    private void postOrder(BinaryTreeNode<T> node, ArrayUnorderedList<T> tempList) {
        if (node != null) {
            tempList.addToRear(node.getElement());
            inOrder(node.getLeft(), tempList);
            inOrder(node.getRight(), tempList);
        }
    }

    @Override
    //为树的层序遍历返回一个迭代器
    public Iterator<T> iteratorLevelOrder() {
        ArrayUnorderedList<BinaryTreeNode<T>> nodes = new ArrayUnorderedList<BinaryTreeNode<T>>();
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        BinaryTreeNode<T> current;

        nodes.addToRear(root);

        while (!nodes.isEmpty()) {
            current = nodes.removeFirst();

            if (current != null) {
                tempList.addToRear(current.getElement());
                if (current.getLeft() != null)
                    nodes.addToRear(current.getLeft());
                if (current.getRight() != null)
                    nodes.addToRear(current.getRight());
            } else
                tempList.addToRear(null);
        }

        return new TreeIterator(tempList.iterator());
    }

    @Override
    public Iterator<T> iterator() {
        return iteratorInOrder();
    }

    //中序输出
    public void toInString(){
        inOrder(root);
    }
    private void inOrder(BinaryTreeNode root) {
        if (null != root) {
            inOrder(root.getLeft());
            System.out.print(root.getElement() + "\t");
            inOrder(root.getRight());
        }
    }

    //前序输出
    public void toPreString(){
        preOrder(root);
    }
    private void preOrder(BinaryTreeNode root){
        if(null!= root){
            System.out.print(root.getElement() + "\t");
            preOrder(root.getLeft());
            preOrder(root.getRight());
        }
    }

    //后序输出
    public void toPostString(){
        postOrder(root);
    }
    private void postOrder(BinaryTreeNode root) {
        if (null != root) {
            postOrder(root.getLeft());
            postOrder(root.getRight());
            System.out.print(root.getElement() + "\t");
        }
    }

    //层序输出递归
    public void toLevelString1(){
        if(root == null)
            return;
        int height = getHeight2();
        for(int i = 1; i <= height; i++){
            levelOrder(root,i);
        }
    }
    private void levelOrder(BinaryTreeNode root,int level){
        if(root == null || level < 1){
            return;
        }
        if(level == 1){
            System.out.print(root.getElement() + "\n");
            return;
        }
        levelOrder(root.getLeft(),level - 1);
        levelOrder(root.getRight(),level - 1);
    }
    //层序输出非递归
    public void toLevelString2(){
        BinaryTreeNode temp;
        Queue<BinaryTreeNode> queue=new LinkedList<BinaryTreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()){
            temp=queue.poll();
            System.out.print(temp.getElement()+"\n");
            if(null!=temp.getLeft())
                queue.offer(temp.getLeft());
            if(null!=temp.getRight()){
                queue.offer(temp.getRight());
            }
        }
    }

    public String toString(){
    UnorderedListADT<BinaryTreeNode<T>> nodes = new ArrayUnorderedList<BinaryTreeNode<T>>();
    UnorderedListADT<Integer> levelList = new ArrayUnorderedList<Integer>();

    BinaryTreeNode<T> current;
    String result = "";
    int printDepth = this.getHeight1();
    int possibleNodes = (int) Math.pow(2, printDepth + 1);
    int countNodes = 0;

    nodes.addToRear(root);
    Integer currentLevel = 0;
    Integer previousLevel = -1;
    levelList.addToRear(currentLevel);

    while (countNodes < possibleNodes) {
        countNodes = countNodes + 1;
        current = nodes.removeFirst();
        currentLevel = levelList.removeFirst();
        if (currentLevel > previousLevel) {
            result = result + "\n\n";
            previousLevel = currentLevel;
            for (int j = 0; j < ((Math.pow(2, (printDepth - currentLevel))) - 1); j++)
                result = result + " ";
        } else {
            for (int i = 0; i < ((Math.pow(2,
                    (printDepth - currentLevel + 1)) - 1)); i++) {
                result = result + " ";
            }
        }
        if (current != null) {
            result = result + (current.getElement()).toString();
            nodes.addToRear(current.getLeft());
            levelList.addToRear(currentLevel + 1);
            nodes.addToRear(current.getRight());
            levelList.addToRear(currentLevel + 1);
        } else {
            nodes.addToRear(null);
            levelList.addToRear(currentLevel + 1);
            nodes.addToRear(null);
            levelList.addToRear(currentLevel + 1);
            result = result + " ";
        }
    }
		return result;
}

    /**
     * Inner class to represent an iterator over the elements of this tree
     */
    private class TreeIterator implements Iterator<T> {
        private int expectedModCount;
        private Iterator<T> iter;

        /**
         * Sets up this iterator using the specified iterator.
         *
         * @param iter
         *            the list iterator created by a tree traversal
         */
        public TreeIterator(Iterator<T> iter) {
            this.iter = iter;
            expectedModCount = modCount;
        }

        /**
         * Returns true if this iterator has at least one more element to
         * deliver in the iteration.
         *
         * @return true if this iterator has at least one more element to
         *         deliver in the iteration
         * @throws ConcurrentModificationException
         *             if the collection has changed while the iterator is in
         *             use
         */
        public boolean hasNext() throws ConcurrentModificationException {
            if (!(modCount == expectedModCount))
                throw new ConcurrentModificationException();

            return (iter.hasNext());
        }

        /**
         * Returns the next element in the iteration. If there are no more
         * elements in this iteration, a NoSuchElementException is thrown.
         *
         * @return the next element in the iteration
         * @throws NoSuchElementException
         *             if the iterator is empty
         */
        public T next() throws NoSuchElementException {
            if (hasNext())
                return (iter.next());
            else
                throw new NoSuchElementException();
        }

        /**
         * The remove operation is not supported.
         *
         * @throws UnsupportedOperationException
         *             if the remove operation is called
         */
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
}